package com.cat.dataStructure03;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-maximum-area-of-a-triangle/
 * @create 2025/11/11 12:01
 * @since JDK17
 */

class Solution43 {
    long calc(int[][] coords, int j) {
        int minX = Integer.MAX_VALUE, maxX = 0;
        Map<Integer, Integer> minY = new HashMap<>();
        Map<Integer, Integer> maxY = new HashMap<>();
        for (var p : coords) {
            int x = p[j], y =  p[1 - j];
            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
            maxY.put(x, Math.max(maxY.getOrDefault(x, 0), y));
            minY.put(x, Math.min(minY.getOrDefault(x, y), y));
        }
        long ans = 0;
        for (var e : minY.entrySet()) {
            int x = e.getKey(), y = e.getValue();
            ans = Math.max(ans, (long) (maxY.get(x) - y) * Math.max(maxX - x, x - minX));
        }
        return ans;
    }

    public long maxArea(int[][] coords) {
        long ans = Math.max(calc(coords, 0), calc(coords, 1));
        return ans > 0 ? ans : -1;
    }
}